Search for: All records

We establish a tantalizing symmetry of certain numbers refining the Narayana numbers. In terms of Dyck paths, this symmetry is interpreted in the following way: if $$w_{n,k,m}$$ is the number of Dyck paths of semilength $$n$$ with $$k$$ occurrences of $UD$ and $$m$$ occurrences of $UUD$, then $$w_{2k+1,k,m}=w_{2k+1,k,k+1-m}$$. We give a combinatorial proof of this fact, relying on the cycle lemma, and showing that the numbers $$w_{2k+1,k,m}$$ are multiples of the Narayana numbers. We prove a more general fact establishing a relationship between the numbers $$w_{n,k,m}$$ and a family of generalized Narayana numbers due to Callan. A closed-form expression for the even more general numbers $$w_{n,k_{1},k_{2},\ldots, k_{r}}$$ counting the semilength-$$n$$ Dyck paths with $$k_{1}$$ $UD$-factors, $$k_{2}$$ $UUD$-factors, $$\ldots$$, and $$k_{r}$$ $$U^{r}D$$-factors is also obtained, as well as a more general form of the discussed symmetry for these numbers in the case when all rise runs are of certain minimal length. Finally, we investigate properties of the polynomials $$W_{n,k}(t)= \sum_{m=0}^k w_{n,k,m} t^m$$, including real-rootedness, $$\gamma$$-positivity, and a symmetric decomposition. 

Abstract We show that the base polytopeP_Mof any paving matroidMcan be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial ofP_M, starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni’s work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation ofstressed-hyperplane relaxationintroduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent. 

Let $$G$$ be a graph with vertex set $$\{1,2,\ldots,n\}$$. Its bond lattice, $BL(G)$, is a sublattice of the set partition lattice. The elements of $BL(G)$ are the set partitions whose blocks induce connected subgraphs of $$G$$. In this article, we consider graphs $$G$$ whose bond lattice consists only of noncrossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley's map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions.